package com.isaiah.list;

import java.util.Iterator;

/**
 * @Title: ${file_name}
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/4/809:32
 */
public class LinkedList<E  extends Comparable> implements Iterable<E>{


    @Override
    public Iterator<E> iterator() {
        return new IteratorImpl();
    }

    /**
     * 定义节点类型
     */
    public class Node{
        /** 数据元素 */
        public E e;
        /**  指向下一个节点的指针 */
        public Node next;

        public Node() {
        }

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    /** 头节点 */
    private Node dumyHead;

    /** 元素个数 */
    private int size;

    public LinkedList() {
        dumyHead = new Node();
    }

    public Node getHead(){
        return dumyHead;
    }
    /**
     * 获取链表中的元素个数
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return this.size == 0;
    }

    /**
     * 在链表头部添加节点
     * @param e
     */
    public void addFirst(E e){
        /*
        // 1. 创建节点
        Node node = new Node(e);
        // 2. 新节点指向原来的头节点
        node.next = head;
        // 3. 头节点重新指向现在的新节点，即现在的新节点成为头节点
        head = node;
        // 4. 维护size加1
        size ++;
        */
        this.add(0, e);
    }

    /**
     * 在链表指定位置添加元素
     * @param index
     * @param e
     */
    public void add(int index, E e){
        // 判断index参数是否合法
        if (index <0 || index > size){
            new IllegalArgumentException("Add element failed, Require index >=0 and index < size");
        }
        // 1. 从头节点遍历链表节点，直到index位置为止
        Node prev = this.dumyHead;
        for (int i =0; i < index; i++){
            prev = prev.next;
        }
        // 2. 创建新节点，并且挂在当前节点之后
        prev.next = new Node(e, prev.next);
        // 3. 维护size加1
        size ++;

    }
    public E get(int index){
        // 1. 从头节点遍历链表节点，直到index位置为止
        Node prev = this.dumyHead;
        for (int i = 0; i < index; i++){
            prev = prev.next;
        }
        // 2. 返回index位置节点的元素
        return prev.e;

    }

    /**
     * 在链表的末尾添加元素
     * @param e
     */
    public void addLast(E e){
        /*
        // 1. 从头节点遍历链表节点，直到最尾节点为止
        Node prev = this.dumyHead;
        while (prev.next!= null){
            prev = prev.next;
        }
        // 2. 创建新节点
        Node node = new Node(e, null);
        // 3. 让最后节点next指向新节点
        prev.next = node;
        // 4. 维护size
        size ++;
        */

        // 调用add方法在size位置添加一个元素，即在链表的末尾添加元素
        this.add(this.size, e);
    }

    /**
     * 判断链表中是否包含指定的元素:
     * @param e
     * @return
     */
    public boolean contains(E e){
        // 从虚拟头节点的next遍历链表节点，直到index位置为止
        Node curr = this.dumyHead;

        while (curr != null){
            if (curr.e.equals(e)){
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    public void removeElement(E e) {

    }
    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        Node current = this.dumyHead.next;
        while (current != null){
            rs.append(current + "->");
            current = current.next;
        }
        rs.append("NULL");
        return rs.toString();
    }

    private class IteratorImpl implements Iterator<E>{
        private Node curr;
        public IteratorImpl(){
            this.curr = dumyHead.next;
        }

        @Override
        public boolean hasNext() {
            return curr.next != null;
        }

        @Override
        public E next() {
            Node nextNode = curr.next;
            return nextNode.e;
        }
    }

}
